\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{listings}
\usepackage{hyperref}

\lstset{
language=MATLAB,                % choose the language of the code
basicstyle=\footnotesize,       % the size of the fonts that are used for the code
numbers=left,                   % where to put the line-numbers
numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
numbersep=5pt,                  % how far the line-numbers are from the code
showspaces=false,               % show spaces adding particular underscores
showstringspaces=false,         % underline spaces within strings
showtabs=false,                 % show tabs within strings adding particular underscores
frame=single,                   % adds a frame around the code
tabsize=2,                      % sets default tabsize to 2 spaces
captionpos=b,                   % sets the caption-position to bottom
breaklines=true,                % sets automatic line breaking
breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
}

\title{CS 4830 Cryptography: Assignment 4} 
\author{Yifan Tong, yt347} 
\date{November 11, 2010}

\begin{document} 
\maketitle 
\newpage
\section{Problem 1} % (fold)
\label{sec:problem_1}
\subsection{Part a}
Sample oracle with input $x$, $x+1$, $x+2$, \ldots
\[g_s(x) = f_s(x) || f_s(x+1)\]
\[g_s(x+1) = f_s(x+1) || f_s(x+2)\]
\[g_s(x+2) = f_s(x+2) || f_s(x+3)\]
\[\ldots\]
A pattern can be observed in that the second half of $g_s(x)$ is identical to the first half of $g_s(x+1$ mod $2^{|s|})$ for any arbitrary x.  As a result, a distinguisher can easily distinguish outputs of $g_s(x)$ obtained from $G$.\\\\
Therefore, \textbf{not} PRF.

\subsection{Part b}
Obtain $g^*(s) = g_{0^{|s|}}(x)$ from $G$.
\[g^*(x) = f_{0^{|s|}}(x)||f_{0^{|s|}}(x)\]
From output of $g^*(x)$, we can determine the output of $f_{0^{|s|}}(x)$.\\\\
Sample oracle with x
\[g_s(x) = f_{0^{|s|}}(x)||f_s(x)\]
There exists a trivial distinguisher D that can determine if the first half of $g_s(x)$ matches $f_{0^{|s|}}(x)$ obtained previously.\\\\
Therefore, \textbf{not} PRF.

\subsection{Part c}
By definition of random, if $s$ is a random seed, then $s_1$ and $s_2$ are both random and uncorrelated.  As a result,
\[f_{s_1}(x) \mbox{ and } f_{s_2}(x)\]
are both pseudorandom and indistinguishable, by definitions of PGF.\\\\
Further, through trivial efficient operations and the following hybrids,
\begin{eqnarray}
\{U_n\}_{2n} &\approx& \{U_n\}_n||\{U_n\}_n \\
\{U_n\}_{2n} &\approx& f_{s_1}(x)||\{U_n\}_n \\
\{U_n\}_{2n} &\approx&f_{s_1}(x)|| f_{s_2}(x)
\end{eqnarray}
It is obvious that,
\[g(x) = f_{s_1}(x)|| f_{s_2}(x)\]
is indistinguishable from random.\\\\
Therefore, $G$ is a \textbf{PRF}.

\subsection{Part d}
Since $s$ and $f_s(x)$ are not uncorrelated, it is possible that $G$ is not a PRF.\\
Given a permutation function,
\[p:\{0, 1\}^n\rightarrow \{0, 1\}^n\]
Construct $\alpha(s)$
\[\alpha(s) = p(s_{n-1})||s_n \mbox{ where $s_{n-1}$ represents the first $n-1$ bits of $s$}\]
Further, $\exists$ PRF $F$ defined as follows,
\[F = \{f_s: \{0, 1\}^{|s|} \oplus\alpha(s)\}\]
$F$ satisfies the condition of being a PRF because there exists non-polynomial number of permutations ($2^{n-1}$) defined by $\alpha(s)$\\\\
Given the construction of $F$, and $G$, all $g_s$ in $G$ will expose the last bit of input, and hence trivially distinguishable.\\\\
Therefore, \textbf{not} PRF.
% section problem_1 (end)

\section{Problem 2} % (fold)
\label{sec:problem_2}
\subsection{Part a}
Given that $m_0$ and $m_1$ are indistinguishable for all $H(m_0, m_1)=1$, then the encryption scheme is also single-message secure.\\\\
\textbf{Proof}:\\
Given any arbitrary $m_i, m_j \in M$, the number of bits that differ between $m_i$ and $m_j$ is at most \textbf{n}, where $n$ is the number of bits in each message.\\
As a result, through efficient operations and at most $n$ hybrids, we can conclude that, for any $m_i$, $m_j$,
\[|\mbox{Pr}[D(\mbox{Enc}(m_i) = 1] - \mbox{Pr}[D(\mbox{Enc}(m_j) = 1]|\leq n\cdot\epsilon(n)\]
Since $\epsilon(\cdot)$ is defined as,
\[\epsilon(n) = \frac{1}{p(n)}\]
for some polynomial, $p$.  We can express $n\cdot\epsilon(n)$ as
\[n\cdot\epsilon(n) = \frac{n}{p(n)}=\frac{1}{q(n)}\]
for some polynomial, $q$.  $q(n)$ still satisfies the definition of $\epsilon(\cdot)$.  Therefore, encryptions that are next-message secure are also single-message secure.
\subsection{Part b}
 By definition of the next-message secure encryption --- Enc$^*$, there exists messages $m$, $m+1$, such that $D$ distinguishes the distributions:
\begin{eqnarray*}
\{k\leftarrow \mbox{Gen}(1^n) &:& \mbox{Enc}^*_k(m)\}\\
\{k\leftarrow \mbox{Gen}(1^n) &:& \mbox{Enc}^*_k(m+1)\}
\end{eqnarray*} 
with probability $\leq \epsilon(n)$.\\\\
Consider two messages $m_0 = 0^n$ and $m_1 = 1^n)$, which requires $2^n$ hybrids.  Further, by definition, with $2^n$ hybrids, $D$ distinguishes the distributions:
\begin{eqnarray*}
\{k\leftarrow \mbox{Gen}(1^n) &:& \mbox{Enc}^*_k(0^n)\}\\
\{k\leftarrow \mbox{Gen}(1^n) &:& \mbox{Enc}^*_k(1^n)\}
\end{eqnarray*} 
with probability $\leq \frac{2^n}{p(n)} \not\in \epsilon(n)$ for some polynomial $p$.  Therefore, this definition of multi-message secure is not single-message secure.\\\\
\textbf{Counter-example}:
Consider the following encryption algorithm,
\[ \mbox{Enc}^*_k(m) = \left\{ \begin{array}{ll}
\mbox{"HELLO WORLD"} & \mbox{w.p. }\frac{m}{2^n};\\
\mbox{Enc}_k(m) & \mbox{otherwise}.\end{array} \right. \]
Where Enc$_k$ is some single-message secure encryption.\\\\
Now consider the encryption distributions given by:
\[\{k\leftarrow\mbox{Gen}(1^n) : \mbox{Enc}^*_k(m)\}\]
The encryption scheme --- Enc$^*_k$ --- is in fact multi-message secure because the following sets of encryptions are indistinguishable, for any $m$:
\begin{eqnarray*}
\{k\leftarrow \mbox{Gen}(1^n) &:& \mbox{Enc}^*_k(m))\}\\
\{k\leftarrow \mbox{Gen}(1^n) &:& \mbox{Enc}^*_k(m+1)\}
\end{eqnarray*}
The sets are indistinguishable because the number of "HELLO WORLD" entries between these adjacent sets differ only by $1$; and the remaining entries are also indistinguishable because they are encrypted with Enc$_k$, a single-message secure encryption.\\\\
Finally, consider the following sets,
\begin{eqnarray*}
\{k\leftarrow \mbox{Gen}(1^n) &:& \mbox{Enc}^*_k(0^n)\}\\
\{k\leftarrow \mbox{Gen}(1^n) &:& \mbox{Enc}^*_k(1^n)\}
\end{eqnarray*}
These sets are \textbf{not} indistinguishable because the set for $0^n$ contains only output of $\{\forall k:$ Enc$_k(0^n)\}$; whereas the set for $1^n$ contains $2^n-1$ entries of "HELLO WORLD".
% section problem_2 (end)
\end{document}
